// $Id: rbtree.h,v 1.3 2006-09-06 09:12:09 nicolasw Exp $

/* Arboles Rojo-Negro.
 * Son abbs balanceados, as�que la bsqueda es siempre O(lg(n))
 * ** Hay que recompilar el m�ulo si se cambia el tipo del nodo **
 */
#ifndef _RBTREE_H
#define _RBTREE_H
#define __DEBUG

typedef struct int_env_entry alfa;

struct rbtree
{
    alfa* elem;
    enum {rojo, negro} color;
    struct rbtree* left;
    struct rbtree* right;
};

/* Crea e inicializa un �bol Rojo-Negro
 */
struct rbtree* rbtnew(void);


/* Libera la memoria reservada para este �bol y sus hijos
 */
struct rbtree* rbtdestroy(struct rbtree* este);

/* Inserta un nuevo nodo en el �bol, manteniendo abb
 * Si ya est�en el �bol, lo reemplaza por el dado.
 */
struct rbtree* rbtinsert(struct rbtree* este, alfa* a);

/* Remueve el nodo a del �bol, manteniendo abb.  Si a no pertenece al
 * �bol, no lo remueve.
 */
struct rbtree* rbtremove (struct rbtree* este, alfa* a);

/* Si el elemento A se encuentra en el �bol, se devuelve 1 y
 * coloca una copia del contenido en el �bol en RES (s�o si
 * RES es distinto de 0).
 * Si no se encuentra el elemento A, se devuelve 0.
 */
int rbtget(const struct rbtree* este, alfa* a, alfa* res);

/* Saca por stdout una representaci� del �bol.*/
void rbtshow(const struct rbtree* este);

#endif
